package oct2013;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class ThreeSum {
	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		int n = num.length;
		Arrays.sort(num);
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < n; ++i) {
			map.put(num[i], i);
		}
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				Integer k = map.get(-num[i] - num[j]);
				// int k = Arrays.binarySearch(num, j + 1, n, -num[i] - num[j]);
				// if (k >= 0) {
				if (k != null && k > j) {
					ArrayList<Integer> list = new ArrayList<Integer>();
					list.add(num[i]);
					list.add(num[j]);
					list.add(num[k]);
					res.add(list);
				}
				while (j + 1 < n && num[j + 1] == num[j])
					j++;
			}
			while (i + 1 < n && num[i + 1] == num[i])
				i++;
		}
		return res;
	}
}
